package String;

import java.util.ArrayList;
import java.util.List;

public class _17_LetterCombinationsofaPhoneNumber {
    List<String> result = new ArrayList<>();
    String[] numberToLetter = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return result;
        }
        backtracking("", digits, 0, digits.length());
        return result;
    }

    public void backtracking(String s,String numbers,int pos,int max) {
        if (pos == max) {
            result.add(s);
        } else {
            int number = Integer.parseInt(numbers.charAt(pos) + "");
            for(int i=0;i<numberToLetter[number].length();i++) {
                String ss = s;
                ss += numberToLetter[number].charAt(i) + "";
                backtracking(ss, numbers, pos + 1, max);
            }
        }
    }
}
